package org.basis.algorithm.promote;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 定义:数组中累积和与最小值的乘积，假设叫做指标A。
 * 给定一个数组，请返回子数组中，指标A最大的值。
 *
 * @author Mr_wenpan@163.com 2022/01/10 22:08
 */
public class AllTimesMinToMax {

    /**
     * 练习：给定一个数组arr，请返回该数组的所有子数组
     * 这里使用暴力解法来求解
     */
    public static List<List<Integer>> getSubArray(int[] arr) {
        if (arr == null || arr.length < 1) {
            return null;
        }
        List<List<Integer>> res = new ArrayList<>();
        // 对于每一个位置上的数都从他自己开始，求包含他自己的子数组
        for (int i = 0; i < arr.length; i++) {
            // 对于每一个i位置的数都求从i位置开始所有包含i位置的子数组
            for (int j = i; j < arr.length; j++) {
                List<Integer> sublist = new ArrayList<>();
                for (int k = i; k <= j; k++) {
                    sublist.add(arr[k]);
                }
                // 添加一个子数组
                res.add(sublist);
            }
        }

        return res;
    }

    /**
     * 暴力解法求指标A最大的值（就是遍历每个子数组，找出子数组中指标A最大的然后返回）
     * 这里暴力解法时间复杂度高，但是能保证一定正确，可以作为对数器用
     */
    public static int max1(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        // 最终返回值（返回最大指标A）
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            // 找到以i位置为起点所有能形成的子数组
            for (int j = i; j < arr.length; j++) {
                int min = Integer.MAX_VALUE;
                int sum = 0;
                // 统计以i位置为起点的所能形成的所有子数组中的最大指标
                for (int k = i; k <= j; k++) {
                    min = Math.min(arr[k], min);
                    sum += arr[k];
                }
                // 得到最大指标
                sum = min * sum;
                res = Math.max(res, sum);
            }
        }

        return res;
    }

    /**
     * 用单调栈来求解，时间复杂度（N）
     */
    public static int max2(int[] arr) {
        int size = arr.length;
        int[] sums = new int[size];
        sums[0] = arr[0];
        // 先求出每个位置到0位置的累加和
        for (int i = 1; i < size; i++) {
            sums[i] = sums[i - 1] + arr[i];
        }
        int max = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();

        // 对于每个i位置，都以该位置为最小值，然后找他的子数组中累加和最大的
        for (int i = 0; i < size; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                int j = stack.pop();
                max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);
            }
            stack.push(i);
        }

        // 如果栈中还有元素，那么这些元素一定是从栈底到栈顶递增的
        while (!stack.isEmpty()) {
            int j = stack.pop();
            max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);
        }
        return max;
    }

    public static int max3(int[] arr) {
        int size = arr.length;
        int[] sums = new int[arr.length];
        sums[0] = arr[0];
        // 先求每个位置到0位置的累加和
        for (int i = 1; i < size; i++) {
            sums[i] = sums[i - 1] + arr[i];
        }

        // 存放的是下标
        Stack<Integer> stack = new Stack<>();
        int max = Integer.MIN_VALUE;
        // 以每个位置为最小值所得到的子数组中的指标A最大的
        for (int i = 0; i < size; i++) {
            while (!stack.isEmpty() && stack.peek() >= arr[i]) {
                Integer popIndex = stack.pop();
                // 求得以popIndex位置为最小值的子数组的最大指标，注意：这是 i - 1，因为是 i 位置上的数来结算的栈中的数，所以累加和应该取i -1 位置
                int sum = (stack.isEmpty() ? sums[i - 1] : sums[i - 1] - sums[stack.peek()]) * arr[popIndex];
                // 取最大值
                max = Math.max(max, sum);
            }
            stack.push(i);
        }

        // 当每个位置都进过栈后，栈中仍然有未弹出的数据
        while (!stack.isEmpty()) {
            Integer popIndex = stack.pop();
            // 注意：这里是size - 1 因为是最后一个位置上的数来结算的栈中剩余的元素，所以累加和应该求到最后一个位置
            int sum = (stack.isEmpty() ? sums[size - 1] : sums[size - 1] - sums[stack.peek()]) * arr[popIndex];
            max = Math.max(sum, max);
        }
        return max;
    }

    public static int[] gerenareRondomArray() {
        int[] arr = new int[(int) (Math.random() * 20) + 10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 101);
        }
        return arr;
    }

    public static void main(String[] args) {
        final int testTimes = 2000000;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = gerenareRondomArray();
            if (max1(arr) != max2(arr)) {
                System.out.println("FUCK!");
                break;
            }
        }

    }
}
